package LRU缓存淘汰;

public class DoubleList {

    public Node head, tail;  // 头尾虚节点
    public int capacity;     // 当前链表的节点数量

    public DoubleList() {
        // 初始化双向链表的头尾虚节点
        head = new Node(0, 0);  // 头节点
        tail = new Node(0, 0);  // 尾节点
        head.next = tail;
        tail.prev = head;
        capacity = 0;  // 初始化容量为0
    }

    // 在链表的末尾添加节点
    public void addLast(Node node) {
        // 插入到尾节点之前
        node.prev = tail.prev;  // 新节点的前驱是尾节点的前驱
        node.next = tail;       // 新节点的后继是尾节点
        tail.prev.next = node;  // 尾节点前驱的后继指向新节点
        tail.prev = node;       // 尾节点的前驱指向新节点
        capacity++;             // 容量加一
    }

    // 删除链表中的第一个节点（head 的下一个节点），并返回该节点
    public Node removeFirst() {
        if (head.next == tail) {
            // 链表为空时，返回null
            return null;
        }
        Node first = head.next;  // 获取第一个节点
        remove(first);           // 调用remove方法删除该节点
        return first;            // 返回被删除的节点
    }

    // 删除指定节点
    public void remove(Node node) {
        node.prev.next = node.next;  // 前驱节点的后继指向当前节点的后继
        node.next.prev = node.prev;  // 后继节点的前驱指向当前节点的前驱
        capacity--;                  // 容量减一
    }

    public void  printList() {
        Node current = head.next;
        while (current!= tail) {
            System.out.print(current.key + " ");
            current = current.next;  // 移动到下一个节点
        }
        System.out.println();
    }
}
